Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 6
з дисципліни «Програмування складних алгоритмів»
Тема «Розріджені матриці»
Варіант № 24
Дата «4» червня 2022
Мета роботи: Метою лабораторної роботи є ознайомитися з основами роботи з розрідженими матрицями і методами їх компактного зберігання .
1.1. Завдання до роботи
Розробити спосіб економного зберігання в пам’яті розріджених матриць.
Виконати індивідуальне завдання над стисненою матрицею. Вивести матрицю до та після обробки у стисненому та розгорнутому вигляді.
Провести обмін елементів матриці за вказаною схемою, будь-яким обраним способом.
/
1.2. Теоретичні відомості
Розріджена матриця — матриця, більша частина елементів якої є нулі. Немає єдиного визначення, яка кількість ненульових елементів має бути в матриці, щоб вона була розрідженою. Для матриці порядку n елементів кількість ненульових елементів:
є O(n). Таке визначення підходить хіба для теоретичного аналізу асимптотичних властивостей матричних алгоритмів.
в кожному рядку не перевищує 10 в типовому випадку.
Обмежено nα+1, де α <1.
Представлення у структурах даних
Зберігати цілу матрицю у пам'яті комп'ютера є неефективно по відношенню до пам'яті, тому є альтернативні способи збереження таких матриць.
Зберігання ненульових елементів
Одним з таких способів полягає в зберіганні ненульових елементів та їх координат. Цей спосіб є економний для пам'яті але для виконання дій з матрицями (додавання, множення) він є неефективний, оскільки кожного разу потрібно перебирати всі елементи для пошуку відповідного елемента.
Зберігання ненульових елементів зв'язаних вказівниками
У цьому способі збереження кожен ненульовий елемент зберігається у вигляді значення, номера рядка та стовпця і вказівника на наступний елемент в рядку і стовпці. Для цього методу збереження потрібно також зберігати рамку, яка складається з таких самих елементів, до якої ми будемо прив'язувати всі елементи вказівниками. Цей спосіб потребує більше пам'яті, але при цьому збільшується швидкість виконання дій над матрицями.
1.3. Результати роботи
Було створенно програму для роботи з розрідженою матрицею, виводяться два види представлення матриці: розріджена і стиснута. Елементи переміщуються відповідно до схеми і знову виводяться дві матриці.
1.4. Лістинг програми
public static void main(String[] args) { int sparseMatrix[][] = { {0, 0, 3, 0, 0, 4}, {0, 0, 5, 7, 0, 1}, {0, 0, 0, 0, 0, 3}, {0, 2, 6, 0, 1, 0} }; System.out.println(ANSI_RED+"Початкова розріджена матриця:"+ANSI_RESET); printArray(sparseMatrix); System.out.println(ANSI_BLUE+"Стиснена матриця:"+ANSI_RESET); int[][] compactMatrix = compression(sparseMatrix); printArray(compactMatrix); System.out.println(ANSI_RED+"\nЗмінена розріджена матриця:"+ANSI_RESET); int[][] array = ExchangeOfElements(sparseMatrix); printArray(array); System.out.println(ANSI_BLUE+"Змінена стиснена матриця:"+ANSI_RESET); int[][] compactMatrix2 = compression(array); printArray(compactMatrix2); } public static int[][] compression(int[][] sparseMatrix) { int size = 0; for (int i = 0; i < sparseMatrix.length; i++) { for (int j = 0; j < sparseMatrix[0].length; j++) { if (sparseMatrix[i][j] != 0) { size++; } } } int compactMatrix[][] = new int[3][size]; // Making of new matrix int k = 0; for (int i = 0; i < sparseMatrix.length; i++) { for (int j = 0; j < sparseMatrix[0].length; j++) { if (sparseMatrix[i][j] != 0) { compactMatrix[0][k] = i; compactMatrix[1][k] = j; compactMatrix[2][k] = sparseMatrix[i][j]; ...
